package DataStructure.DP;

/**
 * @Author：DijaH
 * @Date：2023/4/16 3:12 下午
 * @Version：1.0.0
 * @Description： 最小编辑距离
 * p130
 */
public class code2_minDistance {

    public static int minDistance(String s1,String s2){
        int m = s1.length();
        int n = s2.length();

        int[][] dp = new int[m+1][n+1];
        //base case
        for(int i = 0; i <= m; i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = 0;
        }
        //自顶向下
        for(int i = 1; i <= m;i++){
            for(int j = 1; j < n; j++){
                if(s1.charAt(i-1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1,Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1));
                }
            }
        }
        //返回右上角的值
        return dp[m][n];
    }
}
